package binary_tree.Niu_Ke;

import java.util.Scanner;

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val) {
        this.val = val;
    }
}
public class KY11{
    // 表示当前处理到先序遍历的哪个字符了
    private static int index = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            // 从外部获取了一个先序遍历的结果集字符串
            String str = scanner.nextLine();
            // 就按照先序遍历的方式还原这个二叉树，返回根节点
            TreeNode root = preOrderBuild(str);
            // 按照中序遍历的方式输出二叉树的节点值
            inOrder(root);
            System.out.println();
            index = 0;
        }
    }

    /**
     * 按照中序遍历遍历二叉树，打印节点值
     * @param root
     */
    private static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先递归左子树
        inOrder(root.left);
        // 根
        System.out.print(root.val + " ");
        // 最后递归访问右子树
        inOrder(root.right);
    }

    /**
     * 传入一个字符串str，就能按照先序遍历的方式还原为二叉树，返回二叉树的根节点
     * @param str
     * @return
     */
    private static TreeNode preOrderBuild(String str) {
        // 读取一个字符
        char cur = str.charAt(index);
        if (cur == '#') {
            // 空树，无需创建节点
            return null;
        }
        TreeNode root = new TreeNode(cur);
        index ++;
        root.left = preOrderBuild(str);
        index ++;
        root.right = preOrderBuild(str);
        return root;
    }
}